#ifndef LIST_DOUBLELIST_DOUBLELIST_H
#define LIST_DOUBLELIST_DOUBLELIST_H
#include "DoubleListNode.h"

template<typename Type>
class DoublyList
{
public:
	DoublyList():head(new DoubleListNode<Type>())
	{    //the head node point to itself
		head->m_pprior=head;
		head->m_pnext=head;
	}
	~DoublyList(){
		MakeEmpty();
		delete head;
	}
	void MakeEmpty();		//make the list empty
	int Length();			//get the length of the list
	DoubleListNode<Type>* Find(int n = 0);//find the nth data
	DoubleListNode<Type>* FindData(Type item);   //find the data which is equal to item
	bool Insert(Type item,int n=0);     //insert item in the nth data
	Type Remove(int n=0);   //delete the nth data
	Type Get(int n=0);      //get the nth data
	void Print();           //print the list
private:
	DoubleListNode<Type> *head;
};

template<typename Type> void DoublyList<Type>::MakeEmpty()
{
	DoubleListNode<Type> *pmove=head->m_pnext,*pdel;
	while(pmove!=head)
	{
		pdel=pmove;
		pmove=pdel->m_pnext;
		delete pdel;
	} 
	head->m_pnext=head;
	head->m_pprior=head;
}

template<typename Type> int DoublyList<Type>::Length()
{
	DoubleListNode<Type> *pprior=head->m_pprior,*pnext=head->m_pnext;
	int count=0;
	while(1)
	{
		if(pprior->m_pnext==pnext)
		{
			break;
		}
		if(pprior==pnext&&pprior!=head)
		{
			count++;
			break;
		}
		count+=2;
		pprior=pprior->m_pprior;
		pnext=pnext->m_pnext;
	}
	return count;
}

template<typename Type> 
DoubleListNode<Type>* DoublyList<Type>::Find(int n = 0)
{
	if(n<0)
	{
		cout<<"The n is out of boundary"<<endl;
		return NULL;
	}
	DoubleListNode<Type> *pmove=head->m_pnext;
	for(int i=0;i<n;i++)
	{
		pmove=pmove->m_pnext;
		if(pmove==head)
		{
			cout<<"The n is out of boundary"<<endl;
			return NULL;
		}
	}
	return pmove;
}

template<typename Type> 
bool DoublyList<Type>::Insert(Type item,int n)
{
	if(n<0)
	{
		cout<<"The n is out of boundary"<<endl;
		return 0;
	}
	DoubleListNode<Type> *newnode=new DoubleListNode<Type>(item),*pmove=head;
	if(newnode==NULL)
	{
		cout<<"Application Erorr!"<<endl;
		exit(1);
	}
	for(int i=0;i<n;i++)
	{   //find the position for insert
		pmove=pmove->m_pnext;
		if(pmove==head)
		{
			cout<<"The n is out of boundary"<<endl;
			return 0;
		}
	}

	//insert the data
	newnode->m_pnext=pmove->m_pnext;
	newnode->m_pprior=pmove;
	pmove->m_pnext=newnode;
	newnode->m_pnext->m_pprior=newnode;
	return 1;
}

template<typename Type> 
Type DoublyList<Type>::Remove(int n = 0)
{
	if(n<0)
	{
		cout<<"The n is out of boundary"<<endl;
		exit(1);
	}
	DoubleListNode<Type> *pmove=head,*pdel;
	for(int i=0;i<n;i++)
	{   //find the position for delete
		pmove=pmove->m_pnext;
		if(pmove==head)
		{
			cout<<"The n is out of boundary"<<endl;
			exit(1);
		}
	}

	//delete the data
	pdel=pmove;
	pmove->m_pprior->m_pnext=pdel->m_pnext;
	pmove->m_pnext->m_pprior=pdel->m_pprior;
	Type temp=pdel->m_data;
	delete pdel;
	return temp;
}

template<typename Type> 
Type DoublyList<Type>::Get(int n = 0)
{
	if(n<0)
	{
		cout<<"The n is out of boundary"<<endl;
		exit(1);
	}
	DoubleListNode<Type> *pmove=head;
	for(int i=0;i<n;i++)
	{
		pmove=pmove->m_pnext;
		if(pmove==head)
		{
			cout<<"The n is out of boundary"<<endl;
			exit(1);
		}
	}
	return pmove->m_data;
}

template<typename Type>
void DoublyList<Type>::Print()
{
	DoubleListNode<Type> *pmove=head->m_pnext;
	cout<<"head";
	while(pmove!=head)
	{
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->over"<<endl<<endl<<endl;

}

template<typename Type>
DoubleListNode<Type>* DoublyList<Type>::FindData(Type item)
{
	DoubleListNode<Type> *pprior=head->m_pprior,*pnext=head->m_pnext;
	while(pprior->m_pnext!=pnext && pprior!=pnext){
		//find the data in the two direction
		if(pprior->m_data==item)
		{
			return pprior;
		}
		if(pnext->m_data==item)
		{
			return pnext;
		}
		pprior=pprior->m_pprior;
		pnext=pnext->m_pnext;
	}
	cout<<"can't find the element"<<endl;
	return NULL;
}

#endif